package sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int arr[] = {90, 23, 9, 120, 23, 20, -1, 7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr) {
        int size = arr.length;
        // 步长
        for (int step = size / 2; step > 0; step /= 2) {
            for (int j = step; j < size; j++) {
                if (arr[j] < arr[j - step]) {
                    // 小的移前去
                    int i = j - step;
                    int val = arr[j];
                    while (i >= 0 && arr[i] > val) {
                        arr[i + step] = arr[i];
                        i -= step;
                    }
                    arr[i + step] = val;
                }
            }
        }
    }
}
